// 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

// 返回符合要求的最少分割次数。

// 示例:

// 输入: "aab"
// 输出: 1
// 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

#include <string>
#include <vector>
#include <algorithm>

using std::min;
using std::string;
using std::vector;

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector<vector<bool>> p(n, vector<bool>(n, false));
        vector<int> dp(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = i; // 初始化dp[i]
            for (int j = 0; j <= i; ++j) {
                if (s[i] == s[j] && (i - j < 2 || p[j+1][i-1])) {
                    p[j][i] = true; // s[j:i] 是回文串
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1);
                }
            }
        }
        return dp[n-1];
    }
};

// 动态规划
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> g(n, vector<bool>(n, true));
        for (int i{n - 1}; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = (s[i] == s[j] && g[i + 1][j - 1]);
            }
        }
        vector<int> f(n, INT_MAX);
        for (int i{0}; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j{0}; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = min(f[i], f[j] + 1);
                    }
                }
            }
        }
        return f[n - 1];
    }
};